package Offer;

import java.util.ArrayDeque;
import java.util.Deque;

/*
    剑指 Offer 32 - I. 从上到下打印二叉树
        从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

    思路: 让你使用队列实现层序遍历；使用ArrayDeque或LinkedList都行
* */
public class T32_levelOrder {
    public int[] levelOrder(TreeNode root) {
        if(root==null){
            return new int[0];
        }

        Deque<TreeNode> queue = new ArrayDeque<>();
        int[] array = new int[1010];
        int index = 0;

        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();   //出队
            array[index++] = node.val;

            //左右孩子入队
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        int copy[] = new int[index];

        //返回 数组的 [0,index)
        System.arraycopy(array, 0, copy, 0, index);
        return copy;
    }
}
